#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

int findPivot(int num[], int kth, int size)
{
    int i = -1, j = 0, k = size-1;
    for (j = 0; j <= size-2; j++) {
	if (num[j] < num[k]) swap(num[++i], num[j]);
    }
    swap(num[++i], num[k]);
    return i; 
}

int findkth(int num[], int k, int size)
{
    //if (k == 1) return num[0];
    cout << "-----------------" << endl;
    for (int i = 0; i < size; i++)
	cout << num[i] << " ";
	cout << endl;

    int pivot = findPivot(num, k, size);
    cout << k  << " " << pivot << " " << size << endl;
    for (int i = 0; i < pivot; i++) 
	cout << num[i] << " ";
    cout << endl;
    for (int i = pivot; i < size; i++)
	cout << num[i] << " ";
    cout << endl;

    if (pivot == k) return num[pivot];
    else if (pivot < k) return findkth(num+pivot+1, k - pivot-1, size-pivot-1);
    else return findkth(num, k, pivot);
}


int main(int argc, char **argv)
{
    srand ( time(NULL) );

    int num[20];

    for (int i = 0; i < 1; i++) {
	for (int j = 0; j < 20; j++) {
	    num[j] = rand()%20;
	}
	vector<int> tmp(num, num + 20);
	//sort(tmp.begin(), tmp.end());
	for (int j = 0; j < 20; j++)
	    cout << tmp[j] << " ";
	cout << endl;
	sort(tmp.begin(), tmp.end());
	for (int j = 0; j < 20; j++)
	    cout << tmp[j] << " ";
	cout << endl;
	cout << "6th: " << findkth(num, 5, 20) << endl;
    }

    return 0;
}
